An Internet router classifies incoming packets based on their header fields using a classifier, which is typically implemented as a table of rules. Each classifier rule specifies a pair, (F, A), where F is a filter and A is an action. If an incoming packet matches a filter in the classifier, the associated action specifies what is to be done with this packet. Typical actions include packet forwarding and dropping.
A d-dimensional filter F is a d-tuple, (F[1], F[2], . . . , F[d]), where F[i] is a range that can specify destination addresses, source addresses, port numbers, protocol types, TCP flags, and other information. A packet is said to match filter F, if the packet's header field values fall in the ranges F[1], . . . , F[d]. Since it is possible for a packet to match more than one of the filters in a classifier, a tie breaker is typically used to determine a unique matching filter. In one-dimensional packet classification (i.e., d=1), F[1] is usually specified as a destination address prefix and lookup involves finding the longest prefix that matches the packet's destination address. Although 1-dimensional prefix filters are adequate for destination based packet forwarding, higher dimensional filters are generally required for firewall, quality of service, and virtual private network applications, for example.